package com.zklh.leetcode.dynamic.middle.problem91;

import java.util.regex.Pattern;

/**
 * @ClassName Solution
 * @Description
 * @Author 坐看落花
 * @Date 2020/3/23 10:16
 * @Version 1.0
 **/
public class Solution {
    public int numDecodings(String s) {
        // 去除字符串的 0*前缀, 这里也可以使用replaceFirst, 也可以使用数组进行处理
        if(s.indexOf('0') == 0) {
            return 0;
        }
        // 获取数字的字符数组
        char[] chars = s.toCharArray();
        int[] cache = new int[chars.length];
        // 初始化缓存, 这里将初始化0,1放到递归外主要是为了优化执行效率, 避免每次进行末尾的时候都需要进行判断
        initializeCache(cache,chars);
        return maxDecodeings(chars, chars.length-1, cache);
    }

    /**
     * 获取 从chars[0]到chars[n]的最大解码方法总数, 使用递归, 思想见thinking
     * @param chars 目标字符集
     * @param n 当前索引
     * @param cache 缓存中间结果
     */
    private int maxDecodeings(char[] chars, int n, int[] cache) {
        // 这里表示n已经计算过了, 不需要再次进行计算了, 直接返回
        if (cache[n] != 0) {
            return cache[n];
        }
        /* 这里递归关系的时候 分为两种情况, 一种是当前值为0, 一种是当前值非0, 记得计算出结果之后要将cache[n]更新 */
        // 这里是递归关系, 如果当前值为0 , 可能会直接无效掉 或不变, 或者减少(减少的情况是n-2,n-1可以组成有效的两位数)
        if (chars[n]-48 == 0){
            /* 这里把无效的字符串挑出来 */
            // 这里表示暂时有效, 有可能会不变或者 会导致 -1个元素
            if (chars[n-1]-48 <= 2 && chars[n-1]-48 > 0) {
                // 只要n=0, 则当前的可能性就是n-2的可能性
                cache[n] =  maxDecodeings(chars, n-2, cache);
            } else { // 抛出无效
                return 0;
            }
        } else {// 如果n不为0, 这里需要分为两种情况, 可以和n-1组合和不能和n-1组合
            cache[n] = maxDecodeings(chars, n-1, cache) + ((chars[n-1]-48)*10+(chars[n]-48) <= 26 && (chars[n-1]-48)*10+(chars[n]-48) > 10 ? maxDecodeings(chars, n-2, cache) : 0);
        }
        return cache[n];
    }

    /**
     * 用于初始化缓存, 这里是将缓存的0,1位置填值
     * @param cache
     * @param chars
     */
    private void initializeCache(int[] cache, char[] chars) {
        if (cache.length > 1) {
            cache[0] = 1;
            if (chars[1]-48 == 0) {
                if(chars[0]-48 > 0 && chars[0]-48 < 3) {
                    cache[1] = 1;
                } else {
                    cache[1] = 0;
                }
            } else {
                if ((chars[0]-48)*10+(chars[1]-48) <= 26 && (chars[0]-48)*10+(chars[1]-48) > 10) {
                    cache[1] = 2;
                } else {
                    cache[1] = 1;
                }
            }

        } else if (cache.length > 0) {
            cache[0] = 1;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.numDecodings("01"));
    }
}
